(1) Field of the Invention
The present invention generally relates to a storage management method in an information processing system, and more particularly to a storage management method in an information processing system, such as a computer language processing system and a knowledge base system, in which a list data structure is treated.
(2) Description of Related Art
In general, while a program in which a list data structure is treated is being executed, a large amount of disused lists are generated. Thus, a storage area used for executing the program is expanded due to the large amount of the disused lists. To prevent the storage area used for executing the program from being expanded, the information processing system in which the list data structure is treated has a storage management function for collecting and reclaiming the disused lists. The storage management function is referred to as a garbage collection.
In a conventional garbage collection called a mark/sweep method, accessible list cells in a storage area are marked, and then list cells having no mark are collected and reclaimed in the storage area. In a conventional garbage collection called a reference counting method, a number of references to each of list cells in the storage area is counted. A value of the counted number of references is referred to as a reference count. Each list cell for which the reference count has become zero is collected and reclaimed. In a conventional garbage collection called a copy method, a storage area is divided into a first area and a second area, when the first area is filled with list cells, the list cells are copied from the first area into the second area. In addition, a copy method in which generations of list cells are considered has been also proposed. As the garbage collection is automatically executed when an amount of list cells in the storage area reaches a predetermined value, a programmer can be indifferent to the garbage collection.
However, in the conventional information processing system having the function of the garbage collection, a long time is required for executing the garbage collection. Thus, a speed at which the program is executed decreases, or the program is prevented from being executed. In addition, to the execution of the garbage collection, an extra storage area other than that used for storing the lists is required. Thus, the list cells are unevenly distributed in a virtual storage space and a paging occurs, so that efficiency of processing is caused to deteriorate.
In the conventional information processing system, all the list cells in the storage area are objects of the garbage collection. Thus, the information processing system has a large load when executing the garbage collection. In addition, short-lived list cells each of which becomes disused immediately after generation have to be also collected and reclaimed.